﻿using System;
using System.Collections.Generic;

namespace DataStructuresCSharp.Tree
{
    public class BinaryTreeNode<T>
    {
        public T Data { get; set; }

        public BinaryTreeNode<T> Left { get; set; }

        public BinaryTreeNode<T> Right { get; set; }

        public BinaryTreeNode(T data)
        {
            Data = data;
        }

        public override string ToString()
        {
            return Data.ToString();
        }
    }

    public class BinaryTree<T>
    {
        public BinaryTreeNode<T> Root { get; set; }

        public BinaryTree() { }

        public BinaryTree(IList<T> items, Func<T, bool> isEndNode)
        {
            if (isEndNode(items[0])) return;

            Root = new BinaryTreeNode<T>(items[0]);
            var queue = new Queue<BinaryTreeNode<T>>();
            queue.Enqueue(Root);
            var i = 1;
            while (queue.Count != 0)
            {
                var top = queue.Dequeue();
                if (i < items.Count && !isEndNode(items[i]))
                {
                    top.Left = new BinaryTreeNode<T>(items[i]);
                    queue.Enqueue(top.Left);
                }
                else if (i >= items.Count) break;
                ++i;
                if (i < items.Count && !isEndNode(items[i]))
                {
                    top.Right = new BinaryTreeNode<T>(items[i]);
                    queue.Enqueue(top.Right);
                }
                else if (i >= items.Count) break;
                ++i;
            }
        }

        public void PreOrderTraverse(Action<BinaryTreeNode<T>> visitAction)
        {
            PreOrderTraverse(Root, visitAction);
        }
        private static void PreOrderTraverse(BinaryTreeNode<T> root, Action<BinaryTreeNode<T>> visitAction)
        {
            if (root == null) return;
            visitAction(root);
            PreOrderTraverse(root.Left, visitAction);
            PreOrderTraverse(root.Right, visitAction);
        }

        public void PreOrderTraverseNonRecursive(Action<BinaryTreeNode<T>> visitAction)
        {/*
            根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，
            其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；
            当访问其左子树时，再访问它的右子树。因此其处理过程如下：
             对于任一结点P：
             1)访问结点P，并将结点P入栈;
             2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
             3)直到P为NULL并且栈为空，则遍历结束。
     */
            var p = Root;
            var stack = new Stack<BinaryTreeNode<T>>();
            while (p != null || stack.Count != 0)
            {
                while (p != null)
                {
                    visitAction(p);
                    stack.Push(p);
                    p = p.Left;
                }
                if (stack.Count != 0)
                {
                    p = stack.Pop();
                    p = p.Right;
                }
            }
        }

        public void InOrderTraverse(Action<BinaryTreeNode<T>> visitAction)
        {
            InOrderTraverse(Root, visitAction);
        }
        private static void InOrderTraverse(BinaryTreeNode<T> root, Action<BinaryTreeNode<T>> visitAction)
        {
            if (root == null) return;
            InOrderTraverse(root.Left, visitAction);
            visitAction(root);
            InOrderTraverse(root.Right, visitAction);
        }


        public void InOrderTraverseNonRecursive(Action<BinaryTreeNode<T>> visitAction)
        {
            /*
            根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，
            然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，
            然后按相同的规则访问其右子树。因此其处理过程如下：
               对于任一结点P，
              1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
              2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
              3)直到P为NULL并且栈为空则遍历结束
            */
            var s = new Stack<BinaryTreeNode<T>>();
            var p = Root;
            while (p != null || s.Count != 0)
            {
                while (p != null)
                {
                    s.Push(p);
                    p = p.Left;
                }
                if (s.Count != 0)
                {
                    var top = s.Pop();
                    visitAction(top);
                    p = top.Right;
                }
            }
        }

        public void PostOrderTraverse(Action<BinaryTreeNode<T>> visitAction)
        {
            PostOrderTraverse(Root, visitAction);
        }
        private static void PostOrderTraverse(BinaryTreeNode<T> root, Action<BinaryTreeNode<T>> visitAction)
        {
            if (root == null) return;
            PostOrderTraverse(root.Left, visitAction);
            PostOrderTraverse(root.Right, visitAction);
            visitAction(root);
        }

        public void PostOrderTraverseNonRecursive(Action<BinaryTreeNode<T>> visitAction)
        {
            // 后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，
            // 要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。
            /*
            要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
            如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，
            但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，
            则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，
            左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
            */

            BinaryTreeNode<T> preNode = null;
            var stack = new Stack<BinaryTreeNode<T>>();
            stack.Push(Root);
            while (stack.Count != 0)
            {
                var curNode = stack.Peek();
                if ((curNode.Left == null && curNode.Right == null) ||
                    (preNode != null && (preNode == curNode.Left || preNode == curNode.Right)))
                {
                    visitAction(curNode);  // 如果当前结点没有孩子结点或者孩子节点都已被访问过 
                    stack.Pop();
                    preNode = curNode;      // 如果上一个节点是当前节点的孩子节点，说明当前节点的所有孩子节点已经被访问过了
                }
                else
                {
                    if (curNode.Right != null) stack.Push(curNode.Right);
                    if (curNode.Left != null) stack.Push(curNode.Left);
                }
            }
        }

        /// <summary>
        /// 按层遍历，属于BFS（非递归）
        /// </summary>
        /// <param name="visitAction"></param>
        public void LayerTraverse(Action<BinaryTreeNode<T>> visitAction)
        {
            LayerTraverse(Root, visitAction);
        }
        private static void LayerTraverse(BinaryTreeNode<T> root, Action<BinaryTreeNode<T>> visitAction)
        {
            if (root == null) return;
            var queue = new Queue<BinaryTreeNode<T>>();
            queue.Enqueue(root);
            while (queue.Count != 0)
            {
                var item = queue.Dequeue();
                visitAction(item);
                if (item.Left != null) queue.Enqueue(item.Left);
                if (item.Right != null) queue.Enqueue(item.Right);
            }
        }

        /// <summary>
        /// 递归法将二叉树的左右子树互换 
        /// </summary>
        /// <param name="root"></param>
        public void ExchangeChild()
        {
            ExchangeChild(Root);
        }
        private static void ExchangeChild(BinaryTreeNode<T> root)
        {
            if (root == null) return;
            ExchangeChild(root.Left);
            ExchangeChild(root.Right);
            var temp = root.Left;
            root.Left = root.Right;
            root.Right = temp;
        }

        /// <summary>
        /// 非递归法将二叉树的左右子树互换
        /// </summary>
        public void ExchangeChildNonRecursive()
        {
            ExchangeChildNonRecursive(Root);
        }
        private static void ExchangeChildNonRecursive(BinaryTreeNode<T> root)
        {
            if (root == null) return;
            var stack = new Queue<BinaryTreeNode<T>>();
            stack.Enqueue(root);
            while (stack.Count != 0)
            {
                var curNode = stack.Dequeue();
                var temp = curNode.Left;
                curNode.Left = curNode.Right;
                curNode.Right = temp;
                if (curNode.Right != null) stack.Enqueue(curNode.Right);
                if (curNode.Left != null) stack.Enqueue(curNode.Left);
            }
        }

        /// <summary>
        /// 递归法求叶子结点个数
        /// </summary>
        /// <returns></returns>
        public int GetLeafNodeNum()
        {
            return GetLeafNodeNum(Root);
        }
        private static int GetLeafNodeNum(BinaryTreeNode<T> root)
        {
            if (root == null) return 0;
            if (root.Left == null && root.Right == null) return 1;
            return GetLeafNodeNum(root.Left) + GetLeafNodeNum(root.Right);
        }

        /// <summary>
        /// 非递归法求叶子结点个数
        /// </summary>
        /// <returns></returns>
        public int GetLeafNodeNumNonRecursive()
        {
            if (Root == null) return 0;
            var queue = new Queue<BinaryTreeNode<T>>();
            queue.Enqueue(Root);
            var count = 0;
            while (queue.Count != 0)
            {
                var item = queue.Dequeue();
                if (item.Left == null && item.Right == null)
                {
                    count++;
                    continue;
                }
                if (item.Left != null) queue.Enqueue(item.Left);
                if (item.Right != null) queue.Enqueue(item.Right);
            }
            return count;
        }

        /// <summary>
        /// 递归求二叉树的深度
        /// </summary>
        /// <returns></returns>
        public int GetDepth()
        {
            return GetDepth(Root);
        }
        private static int GetDepth(BinaryTreeNode<T> root)
        {
            if (root == null) return 0;
            var lDepth = GetDepth(root.Left);
            var rDepth = GetDepth(root.Right);
            return (lDepth > rDepth ? lDepth : rDepth) + 1;
        }

        /// <summary>
        ///  递归判断两棵是否等价 
        /// </summary>
        /// <param name="tree"></param>
        /// <returns></returns>
        public bool Equivalent(BinaryTree<T> tree)
        {
            return Equivalent(Root, tree.Root);
        }
        private static bool Equivalent(BinaryTreeNode<T> tree1, BinaryTreeNode<T> tree2)
        {
            if (tree1 == null && tree2 == null) return true;
            if (tree1 != null && tree2 != null)
            {
                return tree1.Data.Equals(tree2.Data)
                       && Equivalent(tree1.Left, tree2.Left)
                       && Equivalent(tree1.Right, tree2.Right);
            }
            return false;
        }

        /// <summary>
        /// 查找某个信息是否在这棵树中
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public bool Contain(T data)
        {
            if (Root == null) return false;
            var queue = new Queue<BinaryTreeNode<T>>();
            queue.Enqueue(Root);
            while (queue.Count != 0)
            {
                var item = queue.Dequeue();
                if (item.Data.Equals(data)) return true;
                if (item.Left != null) queue.Enqueue(item.Left);
                if (item.Right != null) queue.Enqueue(item.Right);
            }
            return false;
        }

        /// <summary>
        /// 递归求树的结点个数  
        /// </summary>
        /// <returns></returns>
        public int GetNodeNum()
        {
            return GetNodeNum(Root);
        }
        private static int GetNodeNum(BinaryTreeNode<T> root)
        {
            if (root == null) return 0;
            return GetNodeNum(root.Left) + GetNodeNum(root.Right) + 1;
        }

        /// <summary>
        /// 非递归求树的结点个数  
        /// </summary>
        /// <returns></returns>
        public int GetNodeNumNonRecursive()
        {
            if (Root == null) return 0;
            var queue = new Queue<BinaryTreeNode<T>>();
            queue.Enqueue(Root);
            var count = 0;
            while (queue.Count != 0)
            {
                var item = queue.Dequeue();
                count++;
                if (item.Left != null) queue.Enqueue(item.Left);
                if (item.Right != null) queue.Enqueue(item.Right);
            }
            return count;
        }
    }

}



